// 单链表：单链表是维护一系列节点的数据结构，其特点是：每个节点包含了数据，同时包含指向链表中下一个节点的指针。
// 双向链表：不同于单链表，双向链表特点：每个节点分除了包含其数据以外，还包含了分别指向其前驱和后继节点的指针。

// 首先，根据双向链表的特点，我们实现一个节点构造函数（节点类）
class Node {
    constructor (data) {
        this.data = data
        this.next = null
        this.prev = null
    }
}

class DobulyLinkedList {
    constructor () {
        this.head = null
        this.tail = null
    }

    // 尾部增加一个节点
    add (item) {
        let node = new Node(item)

        if (!this.head) {
            this.head = node
            this.tail = node
        } else {
            node.prev = this.tail
            this.tail.next = node
            this.tail = node
        }
    }

    // 在链表指定位置添加一个节点
    addAt (index, item) {
        let node = new Node(item)
        let current = this.head
        let counter = 1

        if (index === 0) {
            this.head.prev = node
            node.next = this.head
            this.head = node
        } else {
            while (current) {
                current = current.next
                if (counter === index) {
                    node.prev = current.prev
                    current.prev.next = node
                    node.next = current
                    current.prev = node
                }
                counter++
            }
        }
    }

    // 删除链表指定数据项节点
    remove (item) {
        let current = this.head
        
        while (current) {
            if (current.data === item) {
                // 只有一个节点
                if (current === this.head && current === this.tail) {
                    this.head = null
                    this.tail = null
                } 
                // 目标节点为链表头
                else if (current === this.head) {
                    this.head = this.head.next
                    this.head.prev = null
                }
                else if (current === this.tail) {
                    this.tail = this.tail.prev
                    this.tail.next = null
                }
                else {
                    current.prev.next = current.next
                    current.next.prev = current.prev
                }
            }

            current = current.next
        }
    }

    // 删除链表指定位置节点
    removeAt (index) {
        let current = this.head
        let counter = 1

        if (index === 0) {
            this.head = this.head.next
            this.head.prev = null
        } else {
            while (current) {
                current = current.next
                if (current == this.tail) {
                    this.tail = this.tail.prev
                    this.tail.next = null
                } else if (counter === index) {
                    current.prev.next = current.next
                    current.next.prev = current.prev
                    break
                }

                counter++
            }
        }
    }
}

// let test = new DoublyLinkedList();
// test.add('a');
// test.add('b');
// test.add('c');
// // test.addAt(1, 'new');
// // test.remove('b');
// // test.reverse();
// let index = test.search('a');
// console.log(index);